1. Field of the Invention
The present invention relates to the field of application specific integrated circuit design and more particularly the design of complex circuitry utilizing automatic generation of hardware description language code.
2. Description of the Related Art
A data communications network is the interconnection of two or more communicating entities (i.e., data sources and/or sinks) over one or more data links. A data communications network allows communication between multiple communicating entities over one or more data communications links. The use of lightwave communications carried over fiber optic cables is a popular method of providing high bandwidth communications.
The synchronous optical network (SONET) protocol is among several protocols designed to employ an optical infrastructure. A similar standard to SONET is the Synchronous Digital Hierarchy (SDH) which is the optical fiber standard predominantly used in Europe. There are only minor differences between the two standards. Accordingly, hereinafter any reference to the term SONET refers to both SDH and SONET networks, unless otherwise noted.
SONET utilizes a byte-interleaved multiplexing scheme. Multiplexing enables one physical medium to carry multiple signals. The first step in the SONET multiplexing process involves the generation of the lowest level or base signal. In SONET, this base signal is referred to as synchronous transport signal-level 1, or simply STS-1, which operates at 51.84 Mbps (Megabits per second). Data between adjacent nodes is transmitted in these STS modules. Each STS is transmitted on a link at regular time intervals (for example, 125 microseconds) and grouped into frames. See Bellcore Generic Requirements document GR-253-CORE (Issue 2, December 1995), hereinafter referred to as “SONET Specification.” Higher-level signals are integer multiples of STS-1. An STS-N signal is composed of N byte-interleaved STS-1 signals.
FIG. 1 illustrates the frame format of the STS-1 signal. SONET organizes STS data streams into frames, consisting of transport overhead and a synchronous payload envelope (SPE). The overhead consists of information that allows the network to operate and allow communications between a network controller and nodes. The transport overhead includes framing information, pointers, performance monitoring, communications, and maintenance information. The synchronous payload envelope is the data to be transported throughout the network, from node to node until the data reaches its destination. The SPE is 87 columns wide by 9 rows deep, a total of 783 bytes.
The transport overhead is composed of section overhead and line overhead. Section overhead is accessed, generated and processed by section terminating equipment (STE). Section overhead supports functions such as performance monitoring, local orderwire, and framing. Line overhead is accessed, generated and processed by line terminating equipment (LTE). Line overhead supports functions such as locating the SPE in the frame, multiplexing or concatenating signals, performance monitoring, automatic protection switching, and line maintenance.
Forward error correction (FEC) is incorporated into the SONET frame to decrease bit error rate (BER) on the SONET signal. FEC adds additional information to the data stream to detect and correct any errors that are caused by the transmission system. The additional information is added to each message in a systematic way so that the resultant codewords have a one to one relation to the messages. FEC identifies a block or packet of data that represents the message. The message block size is typically a power of two bits or bytes. Codewords include the message block and the additional information. For every valid codeword there is one and only one message. For example, for an 8-bit message, one bit of additional information is added in the form of an even parity bit. The message (1 0 1 0 1 0 0 0) becomes the codeword (1 0 1 0 1 0 0 0 1). Therefore, the codeword (0 1 1 0 1 0 0 0 0) is not a valid codeword even though it is 9 bits long just like the other codeword. In this example, the resultant codeword supports 29 possible bit patterns, but only 28 of those patterns are valid.
Algorithms used for FEC include convolutional codes, Hamming codes, Reed-Solomon codes, and BCH (Bose-Chaudhuri-Hocquenghem) codes. BCH codes form a large class of powerful random error-correcting cyclic codes, and have the advantage of being robust and very efficient in terms of the relatively low number of check bits required. These check bits are also easily accommodated in the unused SONET overhead byte locations. BCH codes are specified with three primary parameters, n, k, and t, where:                n=block length (the length of the message bits plus the additional check bits)        k=message length (the number of data bits included in a check block)        t=correctable errors (the number of errors per block which the code can correct).        
BCH codes have the property that the block length n is equal to 2m−1, where m is a positive integer. The code parameters are denoted as (n,k). Another parameter often referred to is the “minimum distance” dmin≧2t+1. The minimum distance defines the minimum number of bit positions by which any two code words can differ. The ITU committee responsible for error correction in SONET networks (committee T1X1.5) has developed a standard for FEC in SONET OC-192 systems which implements a triple-error correcting BCH code referred to as BCH-3.
Galois field or finite field mathematics is the mathematical foundation for BCH-based forward error correction. A Galois field is a type of field extension obtained from considering the coefficients and roots of a given polynomial (also known as the root field). The generator polynomial for a t-error correcting BCH code is specified in terms of its roots from the Galois field GF(2m). If α represents the primitive element in GF(2m), then the generator polynomial g(X) for a t-error correcting BCH code of length 2m−1 is the lowest-degree polynomial which has α, α2, α3, . . . , α2t as its roots, i.e., g(αi)=0 for 1≦i≦2t. It can be shown from the foregoing that g(X) must be the least common multiple (LCM) of φ1(X), φ3(X), . . . , φ2t-1(X), where φi(X) is the minimal polynomial of αi.
Decoding of BCH codes likewise requires computations using Galois field arithmetic. Galois field arithmetic can be implemented (in either hardware or software) more easily than ordinary arithmetic because there are no carry operations. The first step in decoding a t-error correction BCH code is to compute the 2t syndrome components S1, S1, . . . , S2t. For a hardware implementation, these syndrome components may be computed with feedback registers that act as a multiply accumulator (MAC). Since the generator polynomial is a product of, at most, t minimal polynomials, it follows that, at most, t feedback shift registers (each consisting of at most m stages) are needed to form the 2t syndrome components, and it takes n clock cycles to complete those computations. It is also necessary to find the error-location polynomial that involves roughly 2t2 additions and 2t2 multiplications. Finally, it is necessary to correct the error(s) which, in the worst case (for a hardware implementation), requires t multipliers shifted n times. Accordingly, circuits that implement BCH codes are typically either quite complex, or require many operations. For example, the BCH-3 iterative algorithm requires up to five separate steps, with each step involving a varying number of computations, and any hardware implementation of BCH-3 must support the maximum possible number of steps/computations. Implementation of the calculations in electronic circuits can be accomplished with serial based hardware. However, performing calculations serially can take multiple clock cycles for operations to complete. Usage of serial techniques to perform many Galois field operations, including multiplication and division, may not meet system performance goals and may require the use of parallel techniques. The design and implementation of parallel circuitry to perform the calculations is often tedious and error prone.